//朴素dijkstra算法题目链接：https://acm.hdu.edu.cn/showproblem.php?pid=2544
//堆优化dijkstra算法题目链接：https://www.luogu.com.cn/problem/P4779
#include <iostream>
#include <cstring>
using namespace std;

const int N = 110;
int g[N][N];
bool st[N];
int dis[N];
int n , m;

int dijkstra()
{
    //初始化距离数组
    memset(dis,0x3f,sizeof dis);
    dis[1] = 0; //起点固定是1
    for(int i = 0 ; i < n ; ++i)
    {
        int t = -1;
        //找到一条未确定的距离数组中最小的点，更新该点的最短路值为已确定状态
        for(int j = 1 ; j <= n ; ++j)
            if(!st[j] && (t == -1 ||  dis[t] > dis[j]))
                t = j;
        st[t] = true;
        //找到上一步所确定点的相连点，并更新它们距离数组的值
        for(int j = 1 ; j <= n ; ++j)
            dis[j] = min(dis[j],dis[t] + g[t][j]);
        //与它们未更新时距离数组的值取一个最小值
    }
    return dis[n];
}
int main()
{
    do{
        cin >> n >> m;
        if(!n && !m) break;
        memset(st , 0 , sizeof st);//初始化st数组
        memset(g,0x3f,sizeof g); //初始化图
        for(int i = 0 ; i < m ; ++i)
        {
            //插入m条边
            int a , b , val;
            cin >> a >> b >> val;
            g[a][b] = g[b][a] = val; //根据题目要求是一个无向图
        }
        int t = dijkstra();
        printf("%d\n",t);
    }while(true);
    return 0;
}